library CycList

//*****************************************************************
//*  CYCLIST
//*
//*  written by: Anitarf
//*
//*  This library provides a circular double linked list, either as
//*  a standalone struct or as a module that can be implement into
//*  other structs. Since the list is circular, there is no first
//*  or last node in it; all nodes are equal and each CycList
//*  instance is a reference to both a single node and the list as
//*  a whole. This greatly simplifies the API as well as the code
//*  of this library. A CycList can still be used to simulate a
//*  linear linked list by simply adding a sentinel node to mark
//*  the start/end of the list.
//*
//*    Examples of use:
//*
//*    # local CycList cl = CycList.create( 4 )
//*  This creates a new CycList node which is also its own list.
//*  The node will store the value 4 in its .data field.
//*
//*    # local integer i = cl.data
//*  This retrieves the value stored in the CycList cl.
//*
//*    # set cl.next = CycList.create( 5 )
//*  This inserts a new node with the data value 5 into an existing
//*  list. The new node will be inserted after the cl node.
//*
//*    # set cl.prev = CycList.create( 3 )
//*  Same as above except that the new node is inserted before cl.
//*
//*    # set cl = cl.next
//*  This sets the cl variable to the next node in the list.
//*
//*    # set cl = cl.prev
//*  This sets the cl variable to the previous node in the list.
//*
//*    # set cl1.next = cl2
//*  This is an example of how individual CycList instances are not
//*  just a reference to a node, but also the whole list. In this
//*  example the entire list that cl2 is a part of will be inserted
//*  after cl1, starting with cl2.
//*  If cl1 and cl2 are already parts of the same list, this line of
//*  code will instead split the list so that cl2 becomes the next
//*  node after cl1 while all the nodes that were between them are
//*  split off into a new list.
//*
//*    # set cl.next=cl
//*  A special case of the above, this simply removes the cl node
//*  from whatever list it is a part of.
//*
//*    # call cl.exclude()
//*  The exclude method does the same thing as setting a CycList's
//*  next or prev value to itself like in the example above, but
//*  since it returns the CycList it was called on it can be used
//*  on the same line as other methods or operators:
//*
//*    # set cl.next = cl.prev.exclude()
//*  In this example, the node before the cl node is removed from
//*  the list and reinserted after the cl node. Since we can do
//*  all this in a single line thanks to the exclude method, there
//*  is no need to store the node before cl to another variable.
//*
//*    # call cl.exclude().destroy()
//*  In this example, only a single node from a list is destroyed.
//*
//*    # call cl.destroy()
//*  This destroys all the nodes on the list that cl is a part of.
//*
//*    # set cl2 = cl1.search( 5 )
//*  The search method looks through the list for a node with a
//*  given data value (5 in this example) and returns it. Returns
//*  0 if the list does not contain any nodes with that data value.
//*
//*    CycList module information:
//*
//*  The implementing struct may not declare any members that are
//*  named next, prev or exclude. For a documented example of how
//*  to implement the module, see the CycList struct.
//*****************************************************************

    module CycList
        private thistype n
        private thistype p

        method operator next takes nothing returns thistype
            return .n
        endmethod

        method operator prev takes nothing returns thistype
            return .p
        endmethod

        private static method get takes nothing returns nothing
            // We need to use a dummy method to get the name of the implementing struct for the debug message.
        endmethod
        //! textmacro CycListInsertDebug
            if this.n==0 or that.n==0 then
                debug call BJDebugMsg("CycList error: attempted to insert an invalid instance of "+SubString(thistype.get.name,3,StringLength(thistype.get.name)-13)+".")
                return
            endif
        //! endtextmacro

        method operator next= takes thistype that returns nothing
            //! runtextmacro CycListInsertDebug()
            set this.n.p=that.p
            set that.p.n=this.n
            set this.n=that
            set that.p=this
        endmethod

        method operator prev= takes thistype that returns nothing
            //! runtextmacro CycListInsertDebug()
            set this.p.n=that.n
            set that.n.p=this.p
            set this.p=that
            set that.n=this
        endmethod

        method exclude takes nothing returns thistype
            set .n.p=.p
            set .p.n=.n
            set .n=this
            set .p=this
            return this
        endmethod

      static if not thistype.CYCLIST_SKIP_INIT then
        private static method onInit takes nothing returns nothing
            local integer i=1
            loop
                exitwhen i>8190
                set thistype(i).n=thistype(i)
                set thistype(i).p=thistype(i)
                set i=i+1
            endloop
        endmethod
      endif
    endmodule

// ================================================================

    struct CycList
        // You may declare this constant boolean before implementing the CycList module,
        // which allows you to skip the module initialization and reduce the map loading
        // time a bit. The downside of doing this is that you must manually initialize
        // CycList nodes by calling the exclude method or you won't be able to use them.
        private static constant boolean CYCLIST_SKIP_INIT = false

        // This line implements the module, which gives the struct next and prev method
        // operators and the exclude method. The rest of the functionality described in
        // the library documentation is provided by the struct, not the module.
        implement CycList

        // This stores the data value attached to this node.
        readonly integer data

        // The create method allocates a new node with the given data value. If module
        // initialization was skipped, the create method also initializes new nodes by
        // calling the exclude method, which sets the node's next and prev values to
        // point to itself rather than to 0.
        static method create takes integer data returns CycList
            local CycList this=CycList.allocate()
            set .data=data
          static if CYCLIST_SKIP_INIT then
            return .exclude()
          endif
            return this
        endmethod

        // Calling the destroy method on a single node will destroy the entire list. Use
        // the exclude method first if you only want to destroy a single node.
        method destroy takes nothing returns nothing
            loop
                exitwhen .next==this
                call .next.exclude().deallocate()
            endloop
            call .deallocate()
        endmethod

        // The search method loops through the list looking for the given data value.
        private static CycList c
        method search takes integer data returns CycList
            set .c=this
            loop
                if .data==data then
                    return this
                endif
                set this=.next
                exitwhen this==.c
            endloop
            return 0
        endmethod
    endstruct

endlibrary
